package com.example.javabasic.suanfa.jiandan.两数之和;

import java.util.*;

/**
 * @description 两数之和
 * @Author Lin FuYuan
 * @date 2020/10/10
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 * <p>
 *  
 * <p>
 * 示例:
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * <p>
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <nums.length ; j++) {
                if(nums[i]+nums[j] == target){
                    int[] n = {i,j};
                    return n;
                }
            }
        }
        return null;
    }



    /**
     * 返回两个数的下标
     * @author Lin FuYuan
     * @param nums
     * @param target
     * @date 2021/4/30
     * @return int[]
     */
    public static int[] twoSum2(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int n = target - nums[i];
            if(map.containsKey(n)){
                return new int[]{map.get(n),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }



    public static List<List<Integer>> allTwoSum(int[] nums, int target){

        List<List<Integer>> list = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //通过第一个数算出第二个数
            int num2 = target - nums[i];
            //如果map中存在第二个数,则添加一条,
            if(map.containsKey(num2)){
                list.add(Arrays.asList(num2,nums[i]));
            }
            map.put(nums[i],i);
        }
        return list;
    }






    public static void main(String[] args) {

        /**
         * 1,  数组 nums  target  n;
         * 2. 遍历数组 nums  取到第一个值
         * 3 第二层遍历  nums  从上层的  下标开始往后遍历
         *  :  i ,   下层  n = i+1  开始 遍历到结束
         *
         * 4. 在第二层 for循环中  加判断  i +n  是否是 target
         * 5 如果 = target 那么 就输出  i 和 n
         *
         *
         *
         */

        /**
         *
         * 第二种解法
         *
         * 1. 遍历nums ,
         * 2  每遍历一个值, 将另一个值 通过 target - 当前值 = 另一个值
         * 3  当前遍历到的值  放入一个map 集合  ,  k 是数组中的值,  v  是 该数的下标
         * 4.  每遍历一个值  都从  map中  contains 方法  查找  另一个值,  当找到的时候  就可以输出  当前值下标和 map 中取到的 v
         *
         *
         */

       /*
        * 两数组和
        * @author Lin FuYuan
        * @param args
        * @date 2021/6/2
        * @return void    0
        * 给出数组 -1, 0, 1, 2, -1, -4
        *  1. 排序  -4 ,-1 ,-1 ,0, 1,2
        * 2 双指针
        * 前面 +后面  =  值
        * 值  比较  目标值  0
        * -2
        */

//
//        for (int i = 0; i < 10; i++) {
//            int target = 0-nums[]i;
//            //两束之和
//
//        }



    }




 }
